package developer.算法.子串.和为K的子数组;

import java.util.HashMap;

/**
 * @author zhangyongkang
 * @time 2025/3/13 15:05
 * @description 给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
 * <p>
 * 子数组是数组中元素的连续非空序列。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [1,1,1], k = 2
 * [[1,1],[1,1]]
 * 输出：2
 * 示例 2：
 * <p>
 * 输入：nums = [1,2,3], k = 3
 * [[1,2],[3]]
 * 输出：2
 */

public class HeweiKdezishuzuAnswer {

    public static void main(String[] args) {
//        System.out.println(subarraySum(new int[]{1, 1, 1}, 2)); //2
//        System.out.println(subarraySum(new int[]{1, 2, 3}, 4)); //0
//
        Solution4 solution3 = new Solution4();
        System.out.println(solution3.subarraySum(new int[]{1, 1, 1, 1}, 2));
        System.out.println(solution3.subarraySum(new int[]{1, 2, 3}, 4));
        System.out.println(solution3.subarraySum(new int[]{1, 3, 3}, 4));

    }

    static class Solution4 {
        int res = 0;

        public int subarraySum(int[] nums, int k) {
            res = 0;
            dfs(nums, k, 0);
            return res;
        }

        private void dfs(int[] nums, int target, int start) {
            if (start == nums.length) {
                return;
            }
            if (target == 0) {
                res++;
            }
            for (int i = start; i < nums.length; i++) {
                dfs(nums, target - nums[i], i + 1);
            }
        }

    }


    static class Solution3 {
        int res;

        public int subarraySum(int[] nums, int k) {
            res = 0;
            dfs(0, nums.length, k, nums);
            return res;
        }

        private void dfs(int start, int end, Integer target, int[] nums) {
            if (start == end) {
                return;
            }
            if (target == 0) {
                res++;
            }
            for (int i = start; i < end; i++) {
                dfs(i + 1, end, target - nums[i], nums);
            }
        }

    }

    //O(n2)
    public static int subarraySum(int[] nums, int k) {
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            int currentVal = nums[i];
            if (currentVal == k) {
                result++;
            }
            for (int j = i + 1; j < nums.length; j++) {
                currentVal += nums[j];
                if (currentVal == k) {
                    result++;
                }
            }
        }
        return result;
    }

    /**
     * 我们可以基于方法一利用数据结构进行进一步的优化，
     * 我们知道方法一的瓶颈在于对每个 i，我们需要枚举所有的 j 来判断是否符合条件，这一步是否可以优化呢？答案是可以的。
     * <p>
     * 我们定义 pre[i] 为 [0..i] 里所有数的和，则 pre[i] 可以由 pre[i−1] 递推而来，即：
     * <p>
     * pre[i]=pre[i−1]+nums[i]
     * 那么「[j..i] 这个子数组和为 k 」这个条件我们可以转化为
     * <p>
     * //     * pre[i]−pre[j−1]==k  -> [j-i]= k  [1-j]+[j-i] = k   -> pre[i] - pre[j-1] = k ;_> pre[i]-k = pre[j-1]
     * 简单移项可得符合条件的下标 j 需要满足
     * <p>
     * pre[j−1]==pre[i]−k
     * 所以我们考虑以 i 结尾的和为 k 的连续子数组个数时
     * 只要统计有多少个前缀和为 pre[i]−k 的 pre[j] 即可。我们建立哈希表 mp，以和为键
     * ，出现次数为对应的值，记录 pre[i] 出现的次数，从左往右边更新 mp 边计算答案，那么以 i 结尾的答案 mp[pre[i]−k] 即可在 O(1) 时间内得到。
     * 最后的答案即为所有下标结尾的和为 k 的子数组个数之和。
     * <p>
     * 需要注意的是，从左往右边更新边计算的时候已经保证了mp[pre[i]−k] 里记录的 pre[j] 的下标范围是 0≤j≤i
     * 。同时，由于pre[i] 的计算只与前一项的答案有关，因此我们可以不用建立 pre 数组，直接用 pre 变量来记录 pre[i−1] 的答案即可。
     * <p>
     * 作者：力扣官方题解
     * 链接：https://leetcode.cn/problems/subarray-sum-equals-k/solutions/238572/he-wei-kde-zi-shu-zu-by-leetcode-solution/
     * 来源：力扣（LeetCode）
     * pre - k = x
     * pre = k +x
     * k = pre -x
     * 7 = 18 - 11
     * 7 = 19 -12
     * x = pre - k  //当前值往前为 11的数量
     *
     * <p>
     * <p>
     * pre - x = k ;
     * <p>
     * [1,2,3]  k = 3
     * pre = 1 k = 2  map = [{0,1},{1,1}]
     * pre =3 k=3  map [{0,1},{1,1},{3,1}]
     * pre =6 k =3 map [{0,1},{1,1},{3,1},{6,1}]
     * <p>
     * pre
     * <p>
     * k = 1
     * 1 2 -2 1 - 5 1
     * count = 1 pre = 1 [{0,1},{1,1}]
     * pre = 2 [{0,1},{1,1},{3,1}]
     * pre = 1 count = 2 [{0,2},{1,1},{3,1}]
     * pre = 2
     *
     * <p>
     * pre[j−1]==pre[i]−k
     * map里面缓存的都是 从 1 开始的数
     * map缓存的核心点在于->
     * 👆  之前有多少个组合是
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     *
     * @param nums
     * @param k
     * @return todo 没看明白 继续理解理解
     */
    public static int subarraySum_official(int[] nums, int k) {
        int count = 0, pre = 0;
        HashMap<Integer, Integer> mp = new HashMap<>();
        mp.put(0, 1);//精髓 如果自身等于k  那么直接+1
        for (int i = 0; i < nums.length; i++) {
            pre += nums[i];//每个结果累加
            if (mp.containsKey(pre - k)) {
                count += mp.get(pre - k);
            }
            mp.put(pre, mp.getOrDefault(pre, 0) + 1);
        }
        return count;
    }

}
